import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:快排
 * User: Admin
 * Date: 2022-05-28
 * Time: 21:46
 */


public class TestDemo {
    /**
     * 区间插入排序
     * @param array
     * @param left
     * @param right
     */
    public static void insertSort(int[] array,int left,int right) {
        for (int i = left+1; i <= right; i++) {
            int tmp = array[i];
            int j = 0;
            for (j = i-1; j >=left ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     *
     * @param array
     * @param left
     * @param right
     * @return 双指针法
     */
    public static int partition2(int[] array,int left,int right) {
        int d = left+1;
        int tmp = array[left];

        for (int i = left+1; i <= right; i++) {
            if(array[i] < tmp) {
                Swap(array,i,d);
                d++;
            }
        }
        Swap(array,d-1,left);
        return d-1;
    }
/**
 * 挖坑法
* */
    public static int partition(int[] array,int low,int hight) {
        int tmp = array[low];
        while(low < hight) {
            while(low < hight && array[hight] >= tmp) {
                hight--;
            }
            array[low] = array[hight];

            while(low <hight && array[low] <= tmp) {
                low++;
            }
            array[hight] = array[low];
        }
        array[low] = tmp;

        return low;
    }
    public static void Swap(int[] array,int left,int right) {
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
    }

    public static int partitionHoare(int[] array,int left,int right) {
        int tmp = array[left];
        int index = left;
        //最后两个相遇代表已经比较到边界
        while(left < right) {

            while(left < right && array[right] >= tmp) {
             right--;
            }

            while(left < right && array[left] <= tmp) {
                left++;
            }

            Swap(array,right,left);
        }
        Swap(array,index,right);
        return right;
    }

    public static void quickSort(int[] array,int left,int right) {
        if(left >= right) return;

        if(right-left+1 < 5 ) {
            insertSort(array,left,right);
            return;
        }
        int pivot = partition2(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

    public static void quick(int[] array) {
        quickSort(array,0,array.length-1);
    }

    public static void main(String[] args) {
        int[] array = {11,88,1,5,10,22,33,55,14,19,33};
        quick(array);
        System.out.println(Arrays.toString(array));
    }
}
